package com.caoyanan.algorithm.question.zuoTraining.training003.class07;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 移除重复字符串，让字典序最小
 * @author: caoyanan
 * @time: 2021/5/21 3:47 下午
 */
public class Question06_RemoveRepeatCharMinLexicographicOrder {

    public static void main(String[] args) {
        int count = 10000;
        //c没了
        minLexicographicOrder("ddcbcdaeba");
        //a有重复
        minLexicographicOrder("babdeaacab");
        for (int i = 0; i < count; i++) {
            String str = LogarithmInputGenerator.getInstance().generateLowerLetterString(10, 5);
            String result = minLexicographicOrder(str);
            System.out.printf("字符串 %s 去除重复字符的最小字典序为 %s\n", str, result);
        }

    }

    private static String minLexicographicOrder(String str) {
        if ("".equals(str)) {
            return "";
        }
        char[] chars = str.toCharArray();
        Map<Character, Integer> charStatistic = new HashMap<>(str.length());
        for (int i = 0; i < chars.length; i++) {
            Integer count = charStatistic.getOrDefault(chars[i], 0);
            charStatistic.put(chars[i], count + 1);
        }
        char choose = 'z';
        int removeLength = 0;
        for (int i = 0; i < chars.length; i++) {
            int chooseCount = charStatistic.get(chars[i]);
            charStatistic.put(chars[i], chooseCount - 1);
            if (choose > chars[i]) {
                choose = chars[i];
                //移走的数量是和选择的字符有关系的
                removeLength = i + 1;
            }
            if (chooseCount == 1) {
                return choose + minLexicographicOrder(str.substring(removeLength)
                        .replaceAll(choose+"", ""));
            }
        }
        return "";
    }
}
